跳到主要内容

L 复杂度类

阐述​

L 是可以用确定性 Turing 机在对数空间内判定的问题的集合。

L=SPACE(log⁡n)\mathrm{L}=\mathrm{SPACE}(\log n)

它的非确定性版本是 NL 复杂度类，

实例​

  • {0k1k∣k≥0}\left\{0^{k} 1^{k} \mid k \geq 0\right\}

性质​

相关内容​

参考文献​